
from itertools import count


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        count_map = dict()
        for c in s:
            count_map.setdefault(c, 0)
            count_map[c] += 1
        
        stack = []

        exist_map = dict()
        for c in s:
            count_map[c] -= 1

            # 已经在stack 当中
            if exist_map.get(c, False) == True:
                continue

            while True:
                if stack and stack[-1] > c and count_map.get(stack[-1], 0) > 0:
                    top = stack[-1]
                    stack.pop()
                    exist_map[top] = False
                else:
                    break
            
            stack.append(c)
            exist_map[c] = True
        
        return "".join(stack)


if __name__ == "__main__":
    s = Solution()
    print(s.removeDuplicateLetters("cbacdcbc"))

